With advances in high throughput sequencing technologies (HTS), billions of
short DNA fragments (also known as ``reads") are processed \emph{in silico} for
genome analysis at a higher rate. To keep up with the high throughput of the
sequencing platforms and to tolerate more errors with shorter fragments, a
faster and error-tolerant DNA read mapper is required.

Many popular modern mappers require the reference genome to be indexed with
different algorithms and data structures in order to enable fast
mapping and high error tolerance. Unfortunately, these mappers are either fast,
error tolerant or memory-efficient but not all three at once. We find that this
is fundamentally due to the different seed lengths the mappers employ, which is
the unit length (in terms of the number of bases) that a mapper uses to index the
reference genome. Mappers that use short seeds (10$\sim$14 bases) are usually
more tolerant to errors, and more memory efficient but also slow whereas
mappers that use long seeds (over 20 bases) are usually fast, but either less
tolerant to errors or less memory efficient. Our goal in this paper is to
design an algorithm and a data structure that obtain the benefits of both short
and long seeds, i.e., fast, tolerant to errors and memory-efficient.

In this paper, we provide a detailed analysis of the effects of using different
seed lengths on the speed, error tolerance and memory efficiency of conventional
mappers and conclude that we need to use both short and long seeds to obtain the
benefits of both. Based on the analysis, we propose simultaneously using seeds with different
lengths in a mapper. We call this idea ``Heterogeneous Seeds''. We also
propose a data structure, called the``Heterogeneous Lookup Table'', and a fragment dividing
algorithm, called ``Jigsaw Seeds and Overlapping Seeds'' to enable mapping with
``Heterogeneous Seeds''.

Our experimental evaluations show that ``Heterogeneous Seeds'' reduce
computation overhead up to 14.8-fold compared to short seeds at 12 bases (2x
compared to long seeds at 20 bases); retain the same level of error tolerance as
short seeds (provide 2x higher error-tolerance compared to long seeds), while
increasing the memory overhead by only 1.5\% compared to short seeds (they
reduce memory overhead by at least 2x compared to long seeds). We conclude that
``Heterogeneous Seeds" approximate the benefits of both short seeds and long
seeds.
